<?php
/**
 * @title 321. 拼接最大数
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }


class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @param Integer $k
     * @return Integer[]
     */
    function maxNumber($nums1, $nums2, $k) {
        /**
         * @since 2020-12-02 长度
         */
        $len1 = count($nums1);
        $len2 = count($nums2);

        /**
         * @since 2020-12-02 结果集
         */
        $result = [];

        /**
         * @since 2020-12-02 全局变量
         */
        $this->nums1 = $nums1;
        $this->nums2 = $nums2;

        $params = [
            [0, $len1-1, 0, $len2-1, $k],
        ];

        /**
         * @since 2020-12-02 层次遍历
         */
        for($i=1; $i<=$k; $i++){
            $max = -1;
            $maxParams = [];

            /**
             * @since 2020-12-03 防止重复
             */
            $hashs = [];
            foreach ($params as $param){
                $key = md5(json_encode($param));
                if(isset($hashs[$key])){
                    continue;
                } else {
                    $hashs[$key] = 1;
                }

                /**
                 * @since 2020-12-03 找最大数
                 */
                list($num, $p) = self::find(...$param);
                if($num > $max){
                    $max = $num;
                    $maxParams = $p;
                } elseif($num == $max) {
                    $maxParams = array_merge($maxParams, $p);
                } else {}
            }

            /**
             * @since 2020-12-02 下次迭代
             */
            $params = $maxParams;
            $result[] = $max;
        }

        /**
         * @return
         */
        return $result;
    }

    /**
     * @title 字符串1,2选出最大值
     * @author start2004
     * @since 2020-12-02 Created
     *
     * @param int $s1
     * @param int $e1
     * @param int $s2
     * @param int $e2
     * @param int $k
     */
    function find($s1 = 0, $e1 = 0, $s2 = 0, $e2 = 0, $k = 0){
        list($max1, $max1Param) = self::find2($s1, $e1, $s2, $e2, $k, 1);
        list($max2, $max2Param) = self::find2($s2, $e2, $s1, $e1, $k, 2);

        /**
         * @since 2020-12-02 比较大小
         */
        if($max1 !== false AND $max2 !== false){
            $param = [$max1Param];
            if($max1 == $max2){
                $param[] = $max2Param;
            } elseif($max2 > $max1) {
                $max1 = $max2;
                $param = [$max2Param];
            } else {}
        } elseif($max1 === false) {
            $max1 = $max2;
            $param = [$max2Param];
        } else {
            $param = [$max1Param];
        }

        /**
         * @return
         */
        return [$max1, $param];
    }


    /**
     * @title 字符串1选出最大数
     * @author start2004
     * @since 2020-12-02 Created
     *
     * @param int $s1
     * @param int $e1
     * @param int $s2
     * @param int $e2
     * @param int $k
     * @return array
     */
    function find2($s1 = 0, $e1 = 0, $s2 = 0, $e2 = 0, $k = 0, $numsKey = 1){
        /**
         * @since 2020-12-02 字符串1无法再取数字
         */
        if($s1 > $e1){
            return [false, false];
        } else {}

        /**
         * @since 2020-12-02 字符串2可以取的剩余长度
         */
        if($s2 > $e2){
            $len2 = 0;
        } else {
            $len2 = $e2-$s2+1;
        }

        /**
         * @since 2020-12-02 从字符串1中取数字的最大key
         */
        $e = min($e1, $e1 - ($k-1-$len2));

        /**
         * @since 2020-12-03 确定数组序号
         */
        if($numsKey == 1){
            $nums = $this->nums1;
        } else {
            $nums = $this->nums2;
        }

        /**
         * @since 2020-12-02 从字符串1找最大值
         */
        $max = -1;
        $maxKey = 0;
        for($i=$s1; $i<=$e; $i++){
            if($nums[$i] > $max){
                $max = $nums[$i];
                $maxKey = $i;
            } else {}
        }

        /**
         * @since 2020-12-02 返回
         */
        if($numsKey == 1){
            return [
                $max,
                [$maxKey+1, $e1, $s2, $e2, $k-1],
            ];
        } else {
            return [
                $max,
                [$s2, $e2, $maxKey+1, $e1, $k-1],
            ];
        }

    }
}


/**
 * @url http://127.0.0.1/leetcode/202012/2020.12.02.php
 */
$datas = [
    [[3, 4, 6, 5], [9, 1, 2, 5, 8, 3], 5,], // 9,8,6,5,3
    [[6, 7], [6, 0, 4], 5,], // 6,7,6,0,4
    [[6, 7], [6, 0, 4], 3,], // 7,6,4
    [[3, 9], [8, 9], 3,], // 9,8,9
    [[8,9,7,3,5,9,1,0,8,5,3,0,9,2,7,4,8,9,8,1,0,2,0,2,7,2,3,5,4,7,4,1,4,0,1,4,2,1,3,1,5,3,9,3,9,0,1,7,0,6,1,8,5,6,6,5,0,4,7,2,9,2,2,7,6,2,9,2,3,5,7,4,7,0,1,8,3,6,6,3,0,8,5,3,0,3,7,3,0,9,8,5,1,9,5,0,7,9,6,8,5,1,9,6,5,8,2,3,7,1,0,1,4,3,4,4,2,4,0,8,4,6,5,5,7,6,9,0,8,4,6,1,6,7,2,0,1,1,8,2,6,4,0,5,5,2,6,1,6,4,7,1,7,2,2,9,8,9,1,0,5,5,9,7,7,8,8,3,3,8,9,3,7,5,3,6,1,0,1,0,9,3,7,8,4,0,3,5,8,1,0,5,7,2,8,4,9,5,6,8,1,1,8,7,3,2,3,4,8,7,9,9,7,8,5,2,2,7,1,9,1,5,5,1,3,5,9,0,5,2,9,4,2,8,7,3,9,4,7,4,8,7,5,0,9,9,7,9,3,8,0,9,5,3,0,0,3,0,4,9,0,9,1,6,0,2,0,5,2,2,6,0,0,9,6,3,4,1,2,0,8,3,6,6,9,0,2,1,6,9,2,4,9,0,8,3,9,0,5,4,5,4,6,1,2,5,2,2,1,7,3,8,1,1,6,8,8,1,8,5,6,1,3,0,1,3,5,6,5,0,6,4,2,8,6,0,3,7,9,5,5,9,8,0,4,8,6,0,8,6,6,1,6,2,7,1,0,2,2,4,0,0,0,4,6,5,5,4,0,1,5,8,3,2,0,9,7,6,2,6,9,9,9,7,1,4,6,2,8,2,5,3,4,5,2,4,4,4,7,2,2,5,3,2,8,2,2,4,9,8,0,9,8,7,6,2,6,7,5,4,7,5,1,0,5,7,8,7,7,8,9,7,0,3,7,7,4,7,2,0,4,1,1,9,1,7,5,0,5,6,6,1,0,6,9,4,2,8,0,5,1,9,8,4,0,3,1,2,4,2,1,8,9,5,9,6,5,3,1,8,9,0,9,8,3,0,9,4,1,1,6,0,5,9,0,8,3,7,8,5],[7,8,4,1,9,4,2,6,5,2,1,2,8,9,3,9,9,5,4,4,2,9,2,0,5,9,4,2,1,7,2,5,1,2,0,0,5,3,1,1,7,2,3,3,2,8,2,0,1,4,5,1,0,0,7,7,9,6,3,8,0,1,5,8,3,2,3,6,4,2,6,3,6,7,6,6,9,5,4,3,2,7,6,3,1,8,7,5,7,8,1,6,0,7,3,0,4,4,4,9,6,3,1,0,3,7,3,6,1,0,0,2,5,7,2,9,6,6,2,6,8,1,9,7,8,8,9,5,1,1,4,2,0,1,3,6,7,8,7,0,5,6,0,1,7,9,6,4,8,6,7,0,2,3,2,7,6,0,5,0,9,0,3,3,8,5,0,9,3,8,0,1,3,1,8,1,8,1,1,7,5,7,4,1,0,0,0,8,9,5,7,8,9,2,8,3,0,3,4,9,8,1,7,2,3,8,3,5,3,1,4,7,7,5,4,9,2,6,2,6,4,0,0,2,8,3,3,0,9,1,6,8,3,1,7,0,7,1,5,8,3,2,5,1,1,0,3,1,4,6,3,6,2,8,6,7,2,9,5,9,1,6,0,5,4,8,6,6,9,4,0,5,8,7,0,8,9,7,3,9,0,1,0,6,2,7,3,3,2,3,3,6,3,0,8,0,0,5,2,1,0,7,5,0,3,2,6,0,5,4,9,6,7,1,0,4,0,9,6,8,3,1,2,5,0,1,0,6,8,6,6,8,8,2,4,5,0,0,8,0,5,6,2,2,5,6,3,7,7,8,4,8,4,8,9,1,6,8,9,9,0,4,0,5,5,4,9,6,7,7,9,0,5,0,9,2,5,2,9,8,9,7,6,8,6,9,2,9,1,6,0,2,7,4,4,5,3,4,5,5,5,0,8,1,3,8,3,0,8,5,7,6,8,7,8,9,7,0,8,4,0,7,0,9,5,8,2,0,8,7,0,3,1,8,1,7,1,6,9,7,9,7,2,6,3,0,5,3,6,0,5,9,3,9,1,1,0,0,8,1,4,3,0,4,3,7,7,7,4,6,4,0,0,5,7,3,2,8,5,1,4,5,8,5,6,7,5,7,3,3,9,6,8,1,5,1,1,1,0,3],500],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->maxNumber(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->($xhprof->listNode($data));
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat(PHP_EOL, 3);
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $result = $obj->$data[0][$i](...$data[1][$i]);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
